package cn.dglydrpy.study.algorithm.od;

import java.util.Scanner;
import java.util.Stack;

/**
 * @author Yyy
 * @date 2024/11/10 16:26
 * @description
 * 荒岛有左右港口和一座连接桥，一群人分别从两港口逃生，向右逃生用正数表示，向左逃生用负数表示，相遇时体力值大的获胜，
 * 相同则同归于尽，赢者继续逃生并减少相应体力，求最终逃生人数。
 输入：
10 20 -20 -5 10
 输出：
 2
 
 输入：
-1 2 5 -6 -3 4
 输出：
 3
 */
public class Od0037_BridgePK {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNextLine()){
            String[] s = scanner.nextLine().split(" ");
            int[] arr = new int[s.length];
            for(int i=0;i<arr.length;i++){
                arr[i] = Integer.valueOf(s[i]);
            }
            
            int ans = myAnswer(arr);
            System.out.println(ans);
        }
    }

    private static int myAnswer(int[] arr) {
        if(arr == null || arr.length == 0){
            return 0;
        }
        
        int ans = 0;
        
        // 先判断可不pk的
        int lastLeftPIndex = -1;
        int lastRightNIndex = -1;
        for(int i = 0;i<arr.length;i++){
            if(arr[i] > 0){
                lastLeftPIndex = i;
                break;
            }
        }
        for(int i = arr.length-1;i>0;i--){
            if(arr[i] < 0){
                lastRightNIndex = i;
                break;
            }
        }
        if(lastLeftPIndex == -1 || lastRightNIndex == -1 || lastLeftPIndex > lastRightNIndex){
            return arr.length;
        }
        
        // -1 2 5 -6 -3 4 
        ans = arr.length - ((lastRightNIndex - lastLeftPIndex) + 1);
        
        // -  +
        Stack<Integer> pStack = new Stack<>();
        for(int i = lastLeftPIndex;i<=lastRightNIndex;i++){
            if(arr[i] > 0){
                pStack.push(arr[i]);
            }else{
                int res = arr[i];
                while (!pStack.isEmpty()){
                    Integer pop = pStack.pop();
                    int pk = pop + res;
                    res = pk;
                    if(pk > 0) {
                        pStack.push(pk);
                        break;
                    }else if(pk == 0){
                        break;
                    }
                }
                if(res < 0){
                    return ans + (lastRightNIndex - i) + 1;
                }
                
            }
        }
        
        return ans + pStack.size();
    }
}
